/*
 * kmeans.cpp
 *
 *  Created on: Dec 13, 2012
 *      Author: filipe mutz
 */
#include "../../util/math_util.h"
#include "kmeans.h"
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <time.h>
#include <math.h>

kmeans_config km_config;

void
allocate_cluster_centroids(clustering_config config, double ***centroids)
{
	(*centroids) = (double **) calloc (config.num_clusters, sizeof(double *));

	for(int i = 0; i < config.num_clusters; i++)
		(*centroids)[i] = (double *) calloc (config.dimension, sizeof(double));
}


int
check_random_point_already_chosen(int points_to_be_centroids[], int num_points_to_check, int random_point)
{
	for(int i = 0; i < num_points_to_check; i++)
		if (points_to_be_centroids[i] == random_point)
			return 1;

	return 0;
}


void
create_random_centroids(clustering_config config, double **points, double **centroids)
{
	int points_to_be_centroids[config.num_clusters];

	srand(time(NULL));

	// esse loop escolhe pontos aleatorios
	// como estimativas iniciais dos centroids
	for(int i = 0; i < config.num_clusters; i++)
	{
		int random_point = rand() % config.num_points;

		while (check_random_point_already_chosen(points_to_be_centroids, i, random_point))
			random_point = rand() % config.num_points;

		memcpy(centroids[i], points[random_point], config.dimension * sizeof(double));

		points_to_be_centroids[i] = random_point;
	}
}


double
check_centroids_not_changed(clustering_config config, double **centroids)
{
	for (int i = 0; i < config.num_clusters; i++)
		for (int j = 0; j < config.dimension; j++)
			if (centroids[i][j] != km_config.last_centroids[i][j])
				return 0;

	return 1;
}


void
copy_centroid_to_last_centroid(clustering_config config, double **centroids)
{
	for (int i = 0; i < config.num_clusters; i++)
		for (int j = 0; j < config.dimension; j++)
			km_config.last_centroids[i][j] = centroids[i][j];
}


int
found_convergence_in_centroids(clustering_config config, double **centroids)
{
	int convergence_is_achieved = 0, max_iteractions_is_achieved = 0;

	// check if the variation in the centroid is less than
	// 1% since the last iteraction
	if (km_config.last_centroids_is_initialized)
		if (check_centroids_not_changed(config, centroids))
			convergence_is_achieved = 1;

	copy_centroid_to_last_centroid(config, centroids);

	km_config.last_centroids_is_initialized = 1;
	km_config.num_iteractions++;

	// check the num of interactions
	if (km_config.num_iteractions >= km_config.num_max_iteractions)
		max_iteractions_is_achieved = 1;

	if (convergence_is_achieved)
	{
		fprintf(stderr, "centroid not changed anymore after %d iteractions\n\n", km_config.num_iteractions);
		return 1;
	}
	else if (max_iteractions_is_achieved)
	{
		fprintf(stderr, "max iteractions achieved after %d iteractions\n\n", km_config.num_iteractions);
		return 1;
	}
	else
		return 0;
}


int
find_closest_centroid_to_the_point(clustering_config config, double *point, double **centroids)
{
	int first_iteraction = 1, closest_centroid_index = 0;
	double dist, closest_centroid_dist = 0;

	for (int i = 0; i < config.num_clusters; i++)
	{
		dist = euclidean_distance(point, centroids[i], config.dimension);

		if (first_iteraction || (dist < closest_centroid_dist))
		{
			closest_centroid_dist = dist;
			closest_centroid_index = i;

			first_iteraction = 0;
		}
	}

	return closest_centroid_index;
}


void
group_points_into_clusters(clustering_config config, double **points, double **centroids, int *cluster_ids)
{
	for(int i = 0; i < config.num_points; i++)
	{
		int closest_centroid = find_closest_centroid_to_the_point(config, points[i], centroids);
		cluster_ids[i] = closest_centroid;
	}
}


void
clean_centroids(clustering_config config, double **centroids)
{
	for(int i = 0; i < config.num_clusters; i++)
		for(int j = 0; j < config.dimension; j++)
			centroids[i][j] = 0.0;
}


void
clean_num_points_per_cluster(clustering_config config, int *num_points_per_cluster)
{
	for(int i = 0; i < config.num_clusters; i++)
		num_points_per_cluster[i] = 0.0;
}


void
calculate_cluster_centroids(clustering_config config, double **centroids, double **points, int *cluster_ids)
{
	int num_points_per_cluster[config.num_clusters];

	clean_centroids(config, centroids);
	clean_num_points_per_cluster(config, num_points_per_cluster);

	for (int i = 0; i < config.num_points; i++)
	{
		int cluster_id = cluster_ids[i];

		for (int j = 0; j < config.dimension; j++)
			centroids[cluster_id][j] += points[i][j];

		num_points_per_cluster[cluster_id]++;
	}

	for (int i = 0; i < config.num_clusters; i++)
	{
		// checa se existe algum ponto no cluster
		// se sim, o algoritmo continua normalmente
		// e o centroide passa a ser a media dos pontos
		// do cluster. caso contrario, um ponto do conjunto
		// eh escolhido randomicamente como centroide
		// de um novo cluster

		if (num_points_per_cluster[i] != 0)
		{
			for (int j = 0; j < config.dimension; j++)
				centroids[i][j] /= num_points_per_cluster[i];
		}
		else
		{
			srand(time(NULL));
			int p = rand() % config.num_points;

			for (int j = 0; j < config.dimension; j++)
				centroids[i][j] /= points[p][j];
		}

	}

}


void
update_centroid_positions(clustering_config config, double **points, double **centroids)
{
	int cluster_ids[config.num_points];

	group_points_into_clusters(config, points, centroids, cluster_ids);
	calculate_cluster_centroids(config, centroids, points, cluster_ids);
}


void
show_centroids_found(clustering_config config, double **centroids)
{
	for(int i = 0; i < config.num_clusters; i++)
	{
		for(int j = 0; j < config.dimension; j++)
			fprintf(stderr, "%lf ", centroids[i][j]);

		fprintf(stderr, "\n");
	}
}


void
find_cluster_centroids(clustering_config config, double **points, double **centroids)
{
	create_random_centroids(config, points, centroids);

	while (!found_convergence_in_centroids(config, centroids))
		update_centroid_positions(config, points, centroids);

	show_centroids_found(config, centroids);
}


void
group_points_to_closest_centroids(clustering_config config, double **points, double **centroids, int *cluster_ids)
{
	#pragma omp parallel for shared(cluster_ids, points, config, centroids)
	for(int i = 0; i < config.num_points; i++)
	{
		int first_iteraction = 1;
		double min_dist = 0;
		int min_index = 0;

		// this loop find the nearest
		// centroid to the point
		for(int j = 0; j < config.num_clusters; j++)
		{
			double dist = euclidean_distance(points[i], centroids[j], config.dimension);

			if ((dist < min_dist) || (first_iteraction == 1))
			{
				first_iteraction = 0;
				min_dist = dist;
				min_index = j;
			}
		}

		cluster_ids[i] = min_index;
	}
}


void
free_centroids(clustering_config config, double **centroids)
{
	for(int i = 0; i < config.num_clusters; i++)
		free(centroids[i]);

	free(centroids);
}


void
initialize_kmeans_configuration(clustering_config config)
{
	km_config.num_iteractions = 0;
	km_config.num_max_iteractions = 100;
	km_config.last_centroids_is_initialized = 0;

	km_config.last_centroids = (double **) calloc (config.num_clusters, sizeof(double *));

	for(int i = 0; i < config.num_clusters; i++)
		km_config.last_centroids[i] = (double *) calloc (config.dimension, sizeof(double));
}


void
kmeans(clustering_config config, double **points, int *cluster_ids)
{
	double **centroids;

	initialize_kmeans_configuration(config);
	allocate_cluster_centroids(config, &centroids);
	find_cluster_centroids(config, points, centroids);
	group_points_to_closest_centroids(config, points, centroids, cluster_ids);
	free_centroids(config, centroids);
}


